有点毒瘤的贪心题,当然也可能是我太菜了。
翻译的挺清楚的了,直接说思路:
我们考虑在读入时顺便把每个数的 权值的二进制最高位预处理出来,同时统计权值和。由于正数变负数和负数变正数本质上是一样的,为了方便考虑,如果 权值和为负数,将所有 取相反数。
随后考虑如何贪心:
枚举每一位,统计二进制最高位为该位的所有数的 权值和。如果这个权值和小于或等于零,那么没有修改该位的必要,因为修改不会使总权值增加,反而可能减少。如果最高位为该位的权值和大于零,那么修改该位比不修改更优。在答案变量中将该位置为 ,并且枚举所有数修改即可。
以上为正解,复杂度 , 为变量范围()。
坑点:贪心时必须从低位到高位枚举每一位进行更新,否则后面的更改可能导致更高位的决策被干扰,得不到正确答案!
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5+5, bit = 62;
ll n, ans;
struct Node {ll val, mask, bits;}a[N];
int main() {
scanf("%llu", &n);
for(ll i=1;i<=n;i++) {
scanf("%lld%lld", &a[i].val, &a[i].mask);
ans += a[i].val;
for(ll _=bit;_+1;_--) if((a[i].mask >> _) & 1) {a[i].bits = _; break;}
}
if(ans < 0) for(ll i=1;i<=n;i++) a[i].val = -a[i].val;
ans = 0;
for(ll _=0;_<=bit;_++) {
ll s = 0;
for(ll i=1;i<=n;i++) s += (a[i].bits == _) * a[i].val;
if(s <= 0) continue;
ans |= (1LL << _);
for(ll i=1;i<=n;i++) a[i].val *= ((a[i].mask >> _) & 1) ? -1 : 1;
}
printf("%lld\n", ans);
// puts("----------\nDEBUG: "); for(ll i=1;i<=n;i++) printf("%lld\n", a[i].val);
return 0;
}